bdfz 2025 winter day1

GCD

GCD CRT 逆元

扩展欧几里得算法（Exgcd）用于求解方程 $ax + by = \gcd(a, b)$ 的整数解 $x$ 和 $y$，同时返回 $a$ 和 $b$ 的最大公约数。以下是代码的逐层解释：

递归终止条件

当 $b = 0$ 时，方程为 $a \cdot 1 + 0 \cdot 0 = a$，此时：

• $x = 1$, $y = 0$

• 直接返回 $a$（最大公约数）

递归过程

1. 递归调用：计算 $\gcd(b, a \% b)$，得到解 $x'$ 和 $y'$，满足：

$$b \cdot x' + (a \% b) \cdot y' = \gcd(b, a \% b)$$

根据欧几里得算法，$\gcd(a, b) = \gcd(b, a \% b)$。

2. 转换解：将递归结果的解 $x'$ 和 $y'$ 转换为当前层的解 $x$ 和 $y$。利用 $a \% b = a - \lfloor a/b \rfloor \cdot b$，原方程可重写为：

$$a \cdot y' + b \cdot (x' - \lfloor a/b \rfloor \cdot y') = \gcd(a, b)$$

因此：

• $x = y'$

• $y = x' - \lfloor a/b \rfloor \cdot y'$

代码步骤

• 保存递归前的 $x$：int t = x（此时 $x = x'$）。

• 更新 $x$：x = y（将 $x$ 设为 $y'$）。

• 更新 $y$：y = t - (a / b) * y（计算 $y = x' - \lfloor a/b \rfloor \cdot y'$）。

示例分析

以 $a = 30$, $b = 12$ 为例：

1. 递归至 $\gcd(6, 0)$，返回 $x = 1$, $y = 0$, $\gcd = 6$。

2. 回溯到 $\gcd(12, 6)$，计算 $x = 0$, $y = 1$，满足 $12 \cdot 0 + 6 \cdot 1 = 6$。

3. 回溯到 $\gcd(30, 12)$，计算 $x = 1$, $y = -2$，满足 $30 \cdot 1 + 12 \cdot (-2) = 6$。

总结

代码通过递归分解问题，逐步缩小规模。每次递归后，利用子问题的解 $x'$ 和 $y'$ 推导当前层的解 $x$ 和 $y$，最终得到满足 $ax + by = \gcd(a, b)$ 的整数解。

CRT